package skewreduce.lib;

import java.util.Collections;
import java.util.List;
import java.util.Random;

public class Util {
    public static enum Axis {
        X, Y, Z;

        public float get(IPoint3D p) { return p.get( ordinal() ); }
        public float get(ITuple p) { return p.getFloat( ordinal() ); }
        public Axis next() {
            int ord = ordinal();
            return ( ord == 0 ) ? Y : ( ord == 1 ) ? Z : X;
        }
        public static Axis get(int i) {
            int ord = i % 3;
            return ( ord == 0 ) ? X : ( ord == 1 ) ? Y : Z;
        }
    }

    private static Random rand;

    static {
        rand = new Random();
    }

    public static <T extends ITuple>
    int partition(T[] values,int left,int right,int pivot,Axis axis,int k) {
        float pv = axis.get(values[pivot]);
        int numDupPvVals = 0;
        T tmp = values[pivot];
        values[pivot] = values[right];
        values[right] = tmp;

        int storeIdx = left;
        for ( int i = left; i < right; ++i ) {
            float v = axis.get(values[i]);
            if ( v < pv ) {
                tmp = values[i];
                values[i] = values[storeIdx];
                values[storeIdx] = tmp;
                ++storeIdx;
            }
            if ( v == pv ) ++numDupPvVals;
        }
        tmp = values[storeIdx];
        values[storeIdx] = values[right];
        values[right] = tmp;
        
        // now we have all values less than pv on the left storeIdx
        // if we have any duplicate pivot values, pack them nearby storeIdx
        int lastIndex = storeIdx;
        if ( numDupPvVals > 0 ) {
            final int limit = storeIdx + numDupPvVals;

        	for ( int i = storeIdx+1; i <= right; ++i ) {
                float v = axis.get(values[i]);
        		if ( pv == v ) {
        			++lastIndex;
        			if ( i != lastIndex ) { // swap only we have to
	        			tmp = values[i];
	        			values[i] = values[lastIndex];
	        			values[lastIndex] = tmp;
        			}
        			if ( lastIndex == limit ) break; // no more duplicate pivot variables
        		}
        	}
        }
        
        // range check
        int destIndex = left + k - 1;
        if ( storeIdx <= destIndex && destIndex <= lastIndex ) {
        	return destIndex;
        }
        return ( destIndex < storeIdx ) ? storeIdx : lastIndex; // skip over duplicate part
    }
    
    public static <T extends ITuple>
    int partition(List<T> values,int left,int right,int pivot,int axis,int k) {
//        float pv = values.get(pivot).getFloat(axis);
//        float minV = pv;
//        float maxV = pv;
//        Collections.swap(values, pivot, right);
//        
//        int storeIdx = left;
//        for ( int i = left; i < right; ++i ) {
//        	float v = values.get(i).getFloat(axis);
//        	if ( v < minV ) minV = v;
//        	if ( v > maxV ) maxV = v;
//            if ( v <= pv ) {
//            	Collections.swap(values, storeIdx, i);
//                ++storeIdx;
//            }
//        }
//        Collections.swap(values,storeIdx,right);
//
//        return ( minV == maxV ) ? -1 : storeIdx;        
        
        float pv = values.get(pivot).getFloat(axis);
        int numDupPvVals = 0;
        Collections.swap(values,pivot,right);

        int storeIdx = left;
        for ( int i = left; i < right; ++i ) {
        	float v = values.get(i).getFloat(axis);
            if ( v < pv ) {
            	Collections.swap(values, storeIdx, i);
                ++storeIdx;
            }
            if ( v == pv ) ++numDupPvVals;
        }
        Collections.swap(values,storeIdx,right);
      
        // now we have all values less than pv on the left storeIdx
        // if we have any duplicate pivot values, pack them nearby storeIdx
        int lastIndex = storeIdx;
        if ( numDupPvVals > 0 ) {
            final int limit = storeIdx + numDupPvVals;

        	for ( int i = storeIdx+1; i <= right; ++i ) {
            	float v = values.get(i).getFloat(axis);
        		if ( pv == v ) {
        			++lastIndex;
        			if ( i != lastIndex ) { // swap only we have to
                    	Collections.swap(values, lastIndex, i);
        			}
        			if ( lastIndex == limit ) break; // no more duplicate pivot variables
        		}
        	}
        }
        
        // range check
        int destIndex = left + k - 1;
        if ( storeIdx <= destIndex && destIndex <= lastIndex ) {
        	return destIndex;
        }
        return ( destIndex < storeIdx ) ? storeIdx : lastIndex; // skip over duplicate part
    }

    
    public static <T extends ITuple>
    int partition(List<T> values,int left,int right,float pv,int axis) {
        int storeIdx = left;
        for ( int i = left; i <= right; ++i ) {
        	float v = values.get(i).getFloat(axis);
            if ( v <= pv ) {
            	Collections.swap(values, storeIdx, i);
                ++storeIdx;
            }
        }

        return storeIdx;
    }
 
    public static <T extends ITuple> 
    int findKMedian(T[] values,int k,int left,int right,Axis axis) {
        int pidx = left + rand.nextInt(right - left+1);
        int p = partition(values,left,right,pidx,axis,k);
        if ( p < 0 ) {
        	throw new IllegalStateException();
        } else {
	        int rank = p - left + 1;
	        if ( rank == k ) {
	            return p;
	        } else if ( rank < k ) {
	            return findKMedian(values, k - rank, p+1, right, axis);
	        } else {
	            return findKMedian(values, k, left, p-1, axis);
	        }
        }
    }
    
    public static <T extends ITuple> 
    int findKMedian(List<T> values,int k,int left,int right,int axis) {
        int pidx = left + rand.nextInt(right - left+1);
        int p = partition(values,left,right,pidx,axis,k);
        if ( p < 0 ) {
        	return k + left - 1;
        } else {
	        int rank = p - left + 1;
	        if ( rank == k ) {
	            return p;
	        } else if ( rank < k ) {
	            return findKMedian(values, k - rank, p+1, right, axis);
	        } else {
	            return findKMedian(values, k, left, p-1, axis);
	        }
        }
    }
}
